import numpy as np
from math import sqrt
from problems import ProblemInstance


class TSPInstance(ProblemInstance):
    """TSP问题实例"""

    def __init__(self, cities):
        self.cities = cities
        self.distance_matrix = self.compute_distance_matrix(cities)

    def compute_distance_matrix(self, cities):
        """计算距离矩阵"""
        n = len(cities)
        dist_matrix = np.zeros((n, n))

        for i in range(n):
            for j in range(i + 1, n):
                dist = sqrt((cities[i][0] - cities[j][0]) ** 2 +
                            (cities[i][1] - cities[j][1]) ** 2)
                dist_matrix[i][j] = dist
                dist_matrix[j][i] = dist

        return dist_matrix

    def evaluate(self, route):
        """评估路径的总距离"""
        total = 0.0
        n = len(route)

        for i in range(n):
            from_city = route[i]
            to_city = route[(i + 1) % n]
            total += self.distance_matrix[from_city][to_city]

        return total

    def get_solution_size(self):
        """获取解的大小"""
        return len(self.cities)

    def get_problem_type(self):
        """获取问题类型"""
        return "tsp"

    def is_feasible(self, solution):
        """检查解是否可行（所有城市恰好访问一次）"""
        return len(set(solution)) == len(solution) and max(solution) == len(self.cities) - 1